package com.future;

/**
 * Description: 378. ��������е� K С��Ԫ�أ���ˢ���17��
 * ����һ��n x n����matrix ������ÿ�к�ÿ��Ԫ�ؾ������������ҵ������е� k С��Ԫ�ء�
 * ��ע�⣬���� ����� �ĵ� k СԪ�أ������ǵ� k �� ��ͬ ��Ԫ�ء�
 * <p>
 * ������ҵ�һ���ڴ渴�Ӷ�����O(n2) �Ľ��������
 * <p>
 *
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
 * �����13
 * ���ͣ������е�Ԫ��Ϊ [1,5,9,10,11,12,13,13,15]���� 8 СԪ���� 13
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/5/15:9:56
 */
public class Solution_378 {

    public static void main(String[] args) {

        int[][] matrix = new int[][]{
                {1, 5, 8, 9, 10},
                {3, 6, 10, 13, 15},
                {7, 8, 15, 16, 20},
                {9, 10, 20, 25, 40},
                {11, 15, 21, 29, 45}
        };
        int k = 10;
        matrix = new int[][]{{-5}};
        k = 1;
       /* matrix = new int[][]{{1, 2}, {3, 3}};
        k = 3;*/
        /**
         * [[1,3,5],[6,7,12],[11,14,14]]
         * 8
         */
        matrix = new int[][]{{1, 3, 5}, {6, 7, 12}, {11, 14, 14}};
        k = 8;
        System.out.println(kthSmallest(matrix, k));
    }

    /**
     * ͨ�����ֲ���
     * ˼·��
     * 1����ȡ��ά���������Сֵ�����м�ֵM
     * 2��ÿ�δ�matrix�����Ͻǿ�ʼ�������ռ���ӽ���С�ڵ���M��ֵnearNum�͸�ֵ�������еĵڼ�Сcount
     * 3���ж�count�Ƿ����k,���ֱ�ӷ���nearNum���������һ���жϣ�
     * 3.1 count>k��˵������L~M-1���䣬��������
     * 3.2 count<k��˵������M+1~R���䣬��������
     *
     * @param matrix
     * @param k
     * @return
     */
    public static int kthSmallest(int[][] matrix, int k) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int N = matrix.length;
        if (N * N < k) {
            return 0;
        }
        int ans = 0;
        int L = matrix[0][0]; // ��Сֵ
        int R = matrix[N - 1][N - 1]; // ���ֵ
        while (L <= R) {

            int M = L + ((R - L) >> 1);
            Info info = getNearInfo(matrix, M);
            if (k == info.count) {
                return info.nearNum;
            }
            if (k < info.count) {
                ans = info.nearNum;
                // R = info.nearNum - 1; ��������д
                R = M - 1;
            } else {
                // L = info.nearNum + 1;��������д
                L = M + 1;
            }
        }
        return ans;
    }

    private static Info getNearInfo(int[][] matrix, int target) {
        int nearNum = Integer.MIN_VALUE;
        int count = 0;
        int N = matrix.length;
        // �����Ͻǳ���
        int row = 0;
        int col = N - 1;
        while (row < N && col >= 0) {
            int val = matrix[row][col];
            if (val <= target) {
                count += col + 1;
                nearNum = Math.max(nearNum, val);
                row++;
            } else {
                col--;
            }
        }
        return new Info(nearNum, count);
    }

    private static class Info {
        // ��ӽ���С�ڵ���ָ��ֵ����
        public int nearNum;
        // С�ڵ���nearNum�ĸ���
        public int count;

        public Info(int nearNum, int count) {
            this.nearNum = nearNum;
            this.count = count;
        }

        @Override
        public String toString() {
            return "Info{" +
                    "nearNum=" + nearNum +
                    ", count=" + count +
                    '}';
        }
    }
}
